Search for: All records

In a primitive integral Apollonian circle packing, the curvatures that appear must fall into one of six or eight residue classes modulo 24. The local-global conjecture states that every sufficiently large integer in one of these residue classes appears as a curvature in the packing. We prove that this conjecture is false for many packings, by proving that certain quadratic and quartic families are missed. The new obstructions are a property of the thin Apollonian group (and not its Zariski closure), and are a result of quadratic and quartic reciprocity, reminiscent of a Brauer-Manin obstruction. Based on computational evidence, we formulate a new conjecture. 

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $$n$$, where $$n$$ is the integer whose factorization is sought. The algorithm has subexponential runtime $$\exp(O(\sqrt{\log n \log \log n}))$$ (or $$\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus. 

Abstract In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small degree endomorphism enables polynomial-time path-finding and endomorphism ring computation (in: Love and Boneh, ANTS XIV-Proceedings of the Fourteenth Algorithmic Number Theory Symposium, volume 4 of Open Book Ser. Math. Sci. Publ., Berkeley, 2020). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (in: Wesolowski, Advances in cryptology-EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science. Springer, Cham, 2022), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don’t assume the knowledge of the primitive order associated with the endomorphism. 

We generalize work by Bourgain and Kontorovich [ On the local-global conjecture for integral Apollonian gaskets , Invent. Math. 196 (2014), 589–650] and Zhang [ On the local-global principle for integral Apollonian 3-circle packings , J. Reine Angew. Math. 737 , (2018), 71–110], proving an almost local-to-global property for the curvatures of certain circle packings, to a large class of Kleinian groups. Specifically, we associate in a natural way an infinite family of integral packings of circles to any Kleinian group $${\mathcal{A}}\leqslant \text{PSL}_{2}(K)$$ satisfying certain conditions, where $$K$$ is an imaginary quadratic field, and show that the curvatures of the circles in any such packing satisfy an almost local-to-global principle. A key ingredient in the proof is that $${\mathcal{A}}$$ possesses a spectral gap property, which we prove for any infinite-covolume, geometrically finite, Zariski dense Kleinian group in $$\operatorname{PSL}_{2}({\mathcal{O}}_{K})$$ containing a Zariski dense subgroup of $$\operatorname{PSL}_{2}(\mathbb{Z})$$ .